Description

207. Course Schedule

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
Return true if you can finish all courses. Otherwise, return false.

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.
Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Constraints:

1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= ai, bi < numCourses
All the pairs prerequisites[i] are unique.

Answer & Explaining

#include <stdio.h>
#include <stdlib.h>

// 建立鄰接表的函數
int** createGraph(int numCourses, int prerequisitesSize, int** prerequisites, int** returnColumnSizes) {
    // 初始化鄰接表和每個節點的列大小
    int** graph = (int**)malloc(numCourses * sizeof(int*));
    *returnColumnSizes = (int*)calloc(numCourses, sizeof(int));

    // 為每個課程建立鄰接表
    for (int i = 0; i < numCourses; i++) {
        graph[i] = (int*)malloc(numCourses * sizeof(int)); // 分配最大容量
    }

    // 填入鄰接表
    for (int i = 0; i < prerequisitesSize; i++) {
        int u = prerequisites[i][1];
        int v = prerequisites[i][0];
        graph[u][(*returnColumnSizes)[u]] = v; // 將課程v加入課程u的鄰接表
        (*returnColumnSizes)[u]++;
    }

    return graph;
}

// DFS函數，用於檢測環
int dfs(int** graph, int* columnSizes, int* visited, int node) {
    if (visited[node] == 1) return 1; // 若節點在訪問中，表示檢測到環
    if (visited[node] == 2) return 0; // 若節點已訪問完成，無環

    visited[node] = 1; // 標記當前節點為訪問中

    // 遍歷當前節點的所有鄰接節點
    for (int i = 0; i < columnSizes[node]; i++) {
        int next = graph[node][i];
        if (dfs(graph, columnSizes, visited, next)) {
            return 1; // 如果檢測到環，返回true
        }
    }

    visited[node] = 2; // 標記當前節點訪問完成
    return 0;
}

// 主函數，判斷是否可以完成所有課程
int canFinish(int numCourses, int** prerequisites, int prerequisitesSize, int* prerequisitesColSize) {
    if (numCourses <= 0) return 0;

    // 建立Graph
    int* columnSizes = NULL;
    int** graph = createGraph(numCourses, prerequisitesSize, prerequisites, &columnSizes);

    // 標記數列，用於記錄節點的visit狀態
    int* visited = (int*)calloc(numCourses, sizeof(int));

    // 遍歷每個節點，進行DFS
    for (int i = 0; i < numCourses; i++) {
        if (visited[i] == 0) { // 若節點尚未訪問
            if (dfs(graph, columnSizes, visited, i)) {
                // 若檢測到環，無法完成課程
                free(visited);
                for (int j = 0; j < numCourses; j++) {
                    free(graph[j]);
                }
                free(graph);
                free(columnSizes);
                return 0;
            }
        }
    }

    // 釋放memory
    free(visited);
    for (int i = 0; i < numCourses; i++) {
        free(graph[i]);
    }
    free(graph);
    free(columnSizes);

    // 沒有環，可以完成所有課程
    return 1;
}

// 測試函數
void runTest(int numCourses, int prerequisitesSize, int prerequisites[][2]) {
    // 將輸入轉換為二維pointer形式
    int** prereqArray = (int**)malloc(prerequisitesSize * sizeof(int*));
    for (int i = 0; i < prerequisitesSize; i++) {
        prereqArray[i] = (int*)malloc(2 * sizeof(int));
        prereqArray[i][0] = prerequisites[i][0];
        prereqArray[i][1] = prerequisites[i][1];
    }
    int* prerequisitesColSize = (int*)malloc(prerequisitesSize * sizeof(int));

    // 呼叫主函數
    int result = canFinish(numCourses, prereqArray, prerequisitesSize, prerequisitesColSize);

    // 輸出結果
    if (result) {
        printf("可以完成所有課程。\n");
    } else {
        printf("無法完成所有課程。\n");
    }

    // 釋放memory
    for (int i = 0; i < prerequisitesSize; i++) {
        free(prereqArray[i]);
    }
    free(prereqArray);
    free(prerequisitesColSize);
}

Testing

#include <stdio.h>
#include <stdlib.h>

// 建立鄰接表的函數
int** createGraph(int numCourses, int prerequisitesSize, int** prerequisites, int** returnColumnSizes) {
    // 初始化鄰接表和每個節點的列大小
    int** graph = (int**)malloc(numCourses * sizeof(int*));
    *returnColumnSizes = (int*)calloc(numCourses, sizeof(int));

    // 為每個課程建立鄰接表
    for (int i = 0; i < numCourses; i++) {
        graph[i] = (int*)malloc(numCourses * sizeof(int)); // 分配最大容量
    }

    // 填入鄰接表
    for (int i = 0; i < prerequisitesSize; i++) {
        int u = prerequisites[i][1];
        int v = prerequisites[i][0];
        graph[u][(*returnColumnSizes)[u]] = v; // 將課程v加入課程u的鄰接表
        (*returnColumnSizes)[u]++;
    }

    return graph;
}

// DFS函數，用於檢測環
int dfs(int** graph, int* columnSizes, int* visited, int node) {
    if (visited[node] == 1) return 1; // 若節點在訪問中，表示檢測到環
    if (visited[node] == 2) return 0; // 若節點已訪問完成，無環

    visited[node] = 1; // 標記當前節點為訪問中

    // 遍歷當前節點的所有鄰接節點
    for (int i = 0; i < columnSizes[node]; i++) {
        int next = graph[node][i];
        if (dfs(graph, columnSizes, visited, next)) {
            return 1; // 如果檢測到環，返回true
        }
    }

    visited[node] = 2; // 標記當前節點訪問完成
    return 0;
}

// 主函數，判斷是否可以完成所有課程
int canFinish(int numCourses, int** prerequisites, int prerequisitesSize, int* prerequisitesColSize) {
    if (numCourses <= 0) return 0;

    // 建立Graph
    int* columnSizes = NULL;
    int** graph = createGraph(numCourses, prerequisitesSize, prerequisites, &columnSizes);

    // 標記數列，用於記錄節點的visit狀態
    int* visited = (int*)calloc(numCourses, sizeof(int));

    // 遍歷每個節點，進行DFS
    for (int i = 0; i < numCourses; i++) {
        if (visited[i] == 0) { // 若節點尚未訪問
            if (dfs(graph, columnSizes, visited, i)) {
                // 若檢測到環，無法完成課程
                free(visited);
                for (int j = 0; j < numCourses; j++) {
                    free(graph[j]);
                }
                free(graph);
                free(columnSizes);
                return 0;
            }
        }
    }

    // 釋放memory
    free(visited);
    for (int i = 0; i < numCourses; i++) {
        free(graph[i]);
    }
    free(graph);
    free(columnSizes);

    // 沒有環，可以完成所有課程
    return 1;
}

// 測試函數
void runTest(int numCourses, int prerequisitesSize, int prerequisites[][2]) {
    // 將輸入轉換為二維pointer形式
    int** prereqArray = (int**)malloc(prerequisitesSize * sizeof(int*));
    for (int i = 0; i < prerequisitesSize; i++) {
        prereqArray[i] = (int*)malloc(2 * sizeof(int));
        prereqArray[i][0] = prerequisites[i][0];
        prereqArray[i][1] = prerequisites[i][1];
    }
    int* prerequisitesColSize = (int*)malloc(prerequisitesSize * sizeof(int));

    // 呼叫主函數
    int result = canFinish(numCourses, prereqArray, prerequisitesSize, prerequisitesColSize);

    // 輸出結果
    if (result) {
        printf("可以完成所有課程。\n");
    } else {
        printf("無法完成所有課程。\n");
    }

    // 釋放memory
    for (int i = 0; i < prerequisitesSize; i++) {
        free(prereqArray[i]);
    }
    free(prereqArray);
    free(prerequisitesColSize);
}

// 主測試函數
int main() {
    // 測試範例1
    int numCourses1 = 2;
    int prerequisites1[][2] = {{1, 0}};
    int prerequisitesSize1 = sizeof(prerequisites1) / sizeof(prerequisites1[0]);
    printf("測試案例1：\n");
    runTest(numCourses1, prerequisitesSize1, prerequisites1);

    // 測試範例2
    int numCourses2 = 2;
    int prerequisites2[][2] = {{1, 0}, {0, 1}};
    int prerequisitesSize2 = sizeof(prerequisites2) / sizeof(prerequisites2[0]);
    printf("\n測試案例2：\n");
    runTest(numCourses2, prerequisitesSize2, prerequisites2);

    // 測試範例3
    int numCourses3 = 4;
    int prerequisites3[][2] = {{1, 0}, {2, 1}, {3, 2}};
    int prerequisitesSize3 = sizeof(prerequisites3) / sizeof(prerequisites3[0]);
    printf("\n測試案例3：\n");
    runTest(numCourses3, prerequisitesSize3, prerequisites3);

    return 0;
}